package com.yww.algorithm.sort;

import java.util.Arrays;

/**
 * @author yww
 * @description 希尔排序（分组插入排序）
 * @since 2024/2/23 16:42
 */
public class ShellSort {
    public static void sort(int[] arr) {
        for (int gap = arr.length >> 1; gap >= 1; gap = gap >> 1) { // 分组
            for (int low = gap; low < arr.length; low++) { // 插入排序
                int i = low - gap;
                int inserted = arr[low];
                while (i >= 0 && arr[i] > inserted) {
                    arr[i + gap] = arr[i];
                    i -= gap;
                }
                if (i != low - gap) {
                    arr[i + gap] = inserted;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {6, 5, 4, 3, 2, 1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
